
#include "mem.h"
#include <stdio.h>

//定义一个数组，在应用中也可以使用外部SRAM 用户可自行修改
static unsigned char ram_heap[MEM_SIZE + (2*SIZEOF_MEM) + MEM_ALIGNMENT];

unsigned char *ram;
struct mem	*ram_end;
struct mem	*lfree;

//内存初始化
void mem_init(void)
{
	struct mem *mem;
	ram = MEM_ALIGN(ram_heap);			//内存对齐
	mem = (struct mem *)(void *)ram;	//在ram的起始位置放置一个mem结构体
	mem->next = MEM_SIZE;				//下一个内存块偏移量为最大值
	mem->prev = 0;						//上一个内存块为空
	mem->used = 0;						//设置未使用标志
	//初始化内存堆中的最后一个内存块，ram_end记录最后一个块的地址
	ram_end = (struct mem *)(void *)&ram[MEM_SIZE];
	ram_end->used = 1;					//标记整体内存块为使用状态
	ram_end->next = MEM_SIZE;			//下一个内存块指向自己	
	ram_end->prev = MEM_SIZE;			//上一个内存块指向自己
	
	lfree = (struct mem *)(void *)ram;	//最低地址空闲块指向第一个控制块
}

//内存申请
void *mem_malloc(mem_size_t size)
{
	mem_size_t ptr, ptr2;							//用于保存某个内存块起始地址的偏移量
	struct mem *mem, *mem2;
	if(size == 0)	return NULL;					//若申请内存长度为0，则返回空指针
	
	/*size要申请的大小*/
	size = MEM_ALIGN_SIZE(size);					//修改size为内存对齐字节数的整数倍
	size = (size <  MIN_SIZE ) ? MIN_SIZE : size;	//申请空间小于最小值，则默认为最小值
	
	if(size > MEM_SIZE) return NULL;				//若大于可申请的最大值，则退出
	
	//互斥信号量
	
	//从lfree开始遍历，找到第一个长度大于size的空闲内存块
	for(ptr = (mem_size_t)((unsigned char *)lfree - ram);	
		ptr < MEM_SIZE - size;								
		ptr = ((struct mem *)&ram[ptr])->next
		)
	{
		mem = (struct mem *)&ram[ptr];

		//若该内存块未使用，且其空间不小于（用户请求大小+系统结构体mem）
		if((!mem->used) && (mem->next - (ptr + SIZEOF_MEM)) >= size)
		{
			//两种执行可能：1.截取内存的一部分分配给用户；2.将剩下内存全部分配给用户
			//若剩余的内存大小大于（要分配尺寸 + MEM大小 + 最小尺寸）则截取
			if(mem->next - (ptr + SIZEOF_MEM) >= (size + SIZEOF_MEM + MIN_SIZE))
			{
				ptr2 = ptr + SIZEOF_MEM + size;				//分配后，剩余空间起始处的偏移量
				mem2 = (struct mem *)(void *)&ram[ptr2];	//剩余空间起始处转为mem结构
				mem2->used = 0;								//标记成未使用
				mem2->next = mem->next;						//将新空闲块插入到原来的链表中
				mem2->prev = ptr;
				mem->next = ptr2;
				mem->used = 1;								//分配给用户的内存块标记为已用
				if(mem2->next != MEM_SIZE)					//若新空闲块不是链表中最后一个
				{
					((struct mem *)&ram[mem2->next])->prev = ptr2;		//将其后一个空闲块的prev指针指向它
				}
			}
			else
			{
				mem->used = 1;								//标记为已用
			}
			//到这里分配完毕，调整指针 lfree
			if(mem == lfree)								//只有 lfree 指向的内存块被分配出去了，才更新 lfree
			{
				//查找链表，得到下一个位置最低的
				while(lfree->used && lfree != ram_end)
				{
					lfree = (struct mem *)&ram[lfree->next];
				}
			}

			return ((unsigned char *)mem + SIZEOF_MEM);
						
		}//if
	}//for
	return NULL;
}

//检查并执行合并操作
void plug_holes(struct mem *mem)
{
	struct mem *nmem;
	struct mem *pmem;
	//查找相邻的下一个内存块
	nmem = (struct mem *)(void *)&ram[mem->next];
	//若下一个内存块空闲且不是系统最后一个空内存块
	if(mem != nmem && nmem->used == 0 && (unsigned char *)nmem != (unsigned char *)ram_end)
	{
		//若lfree指向nmem，则将lfree指向mem	因为合并后，nmem将消失
		if(lfree == nmem)
		{
			lfree = mem;		//执行合并操作，即在链表中删除nmem
		}
		mem->next = nmem->next;
		((struct mem*)(void *)&ram[nmem->next])->prev = (mem_size_t)((unsigned char *)mem - ram);
	}
	//查找相邻的上一个内存块
	pmem =(struct mem *)(void*)&ram[mem->prev];
	if(pmem != mem && pmem->used == 0)	//前一个内存块存在且未用
	{
		//若lfree指向mem，则将lfree 指向pmem
		if(lfree == mem)	lfree = pmem;		//因为合并后，mem将消失
		pmem->next = mem->next;					//执行合并操作，即在链表中删除mem
		((struct mem*)(void *)&ram[mem->next])->prev = (mem_size_t)((unsigned char *)pmem - ram);
	}
}

//内存释放
void free(void * rmem)
{
	struct mem *mem;
	if(rmem == NULL)	return;
	//判断释放空间地址是否合法
	if((unsigned char *)rmem < (unsigned char *)ram || (unsigned char *)rmem >= (unsigned char*)ram_end)
	{
		return;
	}
	mem = (struct mem *)((unsigned char *)rmem - SIZEOF_MEM);
	mem->used = 0;
	//若释放的地址比lfree低，则更新lfree的值
	if(mem < lfree)  lfree = mem;
	//调用该函数，检查并执行合并操作
	plug_holes(mem);
}


